import Foundation


public class String_Practice {
    
    // MARK: - 字符串反转
    /**
     * 字符串反转
     * 1. 把字符串转换为Character数组
     * 2. 左右指针, 交换数组索引位置
     * 3. 返回字符串
     */
    public static func reverseStrings(_ s: String) -> String {
        var charaters: [Character] = Array(s)
        var left = 0
        var right = s.count - 1
        while left < right {
            charaters.swapAt(left, right)
            left += 1
            right -= 1
        }
        return String(charaters)
    }
    
    
    
    // MARK: - 一个字符串中第一个只出现一次的字符
    public static func firstUniqChar(_ s: String) -> Character? {
        var dic = [Character: Int]()
        for char in s {
            dic[char, default: 0] += 1;
        }
        for char in s {
            if dic[char] == 1 {
                return char
            }
        }
        return nil
    }
    
    
    
    // MARK: - 验证回文字符串
    /// 1. 创建左右双指针, 字符串转字符数组
    /// 2. left  小于 right 遍历, 并判断取出两端非符号的字母
    /// 3. 如果两侧有不同, 即非回文字符串
    public static func isPalindrome(_ s: String) -> Bool {
        var left = s.startIndex
        var right = s.index(before: s.endIndex)
        while left < right {
            // 跳过左侧非字母数字指针
            while left < right && !s[left].isLetter && !s[left].isNumber {
                left = s.index(after: left)
            }
            // 跳过右侧
            while left < right && !s[right].isLetter && !s[right].isNumber {
                right = s.index(before: right)
            }
            
            print("\(s[left]) \(s[right])")

            // 判断非回文
            if s[left].lowercased() != s[right].lowercased() {
                return false
            }
            
            // 移动指针
            left = s.index(after: left)
            right = s.index(before: right)
        }
        return true
    }
    
    public static func isPalindrome2(_ s: String) -> Bool {
        let charArr = Array(s)
        // 左右指针
        var left = 0
        var right = charArr.count - 1
        // 遍历
        while left < right {
            // 寻找左侧有效字符
            while left < right && !charArr[left].isNumber && !charArr[left].isLetter {
                left += 1
            }
            // 寻找右侧有效字符
            while left < right && !charArr[right].isNumber && !charArr[right].isLetter {
                right -= 1
            }
            
//            print("\(#function) \(charArr[left]) \(charArr[right])")
            // 对比是否相等
            if charArr[left].lowercased() != charArr[right].lowercased() {
                return false
            }
            
            // 继续移动指针
            left += 1
            right -= 1
        }
        return true
    }
    
    // MARK: - 字符串解码
    /// 1. 如果是数字, 将数字转化为整数, 用于后续计算
    /// 2. 如果是字符, 延长当前字符串
    /// 3. 如果是[, 当前状态入栈
    /// 4. 如果是 ] , 弹出状态, 组合字符串
    public static func decodeString(_ s: String) -> String {
        var stack: [(Int, String)] = []  // 用栈来存储数字和当前的字符串
        var currentString = ""  // 当前正在处理的字符串
        var currentNumber = 0  // 当前数字，用于表示重复次数
        for char in s {
            if let digit = char.wholeNumberValue {
                // 如果是数字，更新当前的数字
                currentNumber = currentNumber * 10 + digit
            } else if char == "[" {
                // 遇到左括号，表示新的一层开始
                stack.append((currentNumber, currentString))
                currentString = ""  // 清空当前字符串，准备接收新的部分
                currentNumber = 0  // 重置数字
            } else if char == "]" {
                // 遇到右括号，表示一层结束
                if let (repeatCount, previousString) = stack.popLast() {
                    // 将解码后的字符串重复相应次数
                    currentString = previousString + String(repeating: currentString, count: repeatCount)
                }
            } else {
                // 普通字符，直接拼接到当前字符串
                currentString.append(char)
            }
        }
        
        return currentString
    }
    
    // MARK: - 是否为子序列
    public static func isSubsequence(_ s: String, _ t: String) -> Bool {
        let sChars = Array(s)
        let tChars = Array(t)
        
        var sIndex = 0
        var tIndex = 0
        
        // 遍历t, 尝试匹配s
        while sIndex < sChars.count && tIndex < tChars.count {
            if sChars[sIndex] == tChars[tIndex] {
                // 移动s的指针
                sIndex += 1
            }
            // 移动t的指针
            tIndex += 1
        }
        
        return sIndex == sChars.count
    }
}
